package genetischeralgorithmus;

import java.util.*;
import java.awt.*;
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author Dominik
 */
public class Recombination {

    public Recombination() {
    }

    public Entity[] crossover(Entity[][] crossPairs, int crossoverMethode) {

        switch (crossoverMethode) {


            case 0:  //PMX (Partially-Mapped-Crossover
                return pmx(crossPairs);
            case 1:  //OX (Order-Crossover)
                return ox(crossPairs);
            case 2:   //AP (Alternating-Position-Crossover)
                return ap(crossPairs);
            case 3:  //CX (Cycle-Crossover)
                return cx(crossPairs);

        }




        return null;
    }

    public Entity[] pmx(Entity[][] crossPairs) {

        Entity[] newOffspring = new Entity[crossPairs.length];

        for (int breedingCount = 0; breedingCount < crossPairs.length; breedingCount++) {

            Random rand1 = new Random();
            int position1 = 0;
            int position2 = 0;
            int l = 0;
            int crossoverPoint1 = 0;
            int crossoverPoint2 = 0;
            int place1 = 0;
            int place2 = 0;
            Entity entity1 = crossPairs[breedingCount][0];
            Entity entity2 = crossPairs[breedingCount][1];


            Entity newEntity = new Entity(entity1.getPath().length);

            crossoverPoint1 = rand1.nextInt(entity1.getPath().length - 1);
            crossoverPoint2 = getRandomWithoutX(crossoverPoint1, entity1.getPath().length - 1);

            if (crossoverPoint2 < crossoverPoint1) {
                l = crossoverPoint1;
                crossoverPoint1 = crossoverPoint2;
                crossoverPoint2 = l;
            }


            for (int i = 0; i < entity1.getPath().length; i++) {
                newEntity.setPath(entity1.getPath());
            }
            for (int i = crossoverPoint1; i <= crossoverPoint2; i++) {


                place1 = entity1.getPath()[i];
                place2 = entity2.getPath()[i];


                for (int k = 0; k < entity1.getPath().length; k++) {
                    if (newEntity.getPath()[k] == place1) {
                        position1 = k;
                    } else if (newEntity.getPath()[k] == place2) {
                        position2 = k;
                    }
                }
                if (place1 != place2) {

                    newEntity.setPlace(place2, position1);
                    newEntity.setPlace(place1, position2);
                }
            }

            newOffspring[breedingCount] = newEntity;
        }
        return newOffspring;
    }

    public Entity[] ox(Entity[][] crossPairs) {

        Entity[] newOffspring = new Entity[crossPairs.length];

        for (int breedingCount = 0; breedingCount < crossPairs.length; breedingCount++) {

            Random rand1 = new Random();
            int l = 0;
            int crossoverPoint1 = 0;
            int crossoverPoint2 = 0;

            int[] mum = crossPairs[breedingCount][0].getPath();
            int[] dad = crossPairs[breedingCount][1].getPath();
            int[] child = new int[dad.length];
            Arrays.fill(child, 0);
            int place1 = 0;
            int place2 = 0;

            Entity newEntity = new Entity(dad.length);

            crossoverPoint1 = rand1.nextInt(dad.length - 1);
            crossoverPoint2 = getRandomWithoutX(crossoverPoint1, dad.length - 1);

            if (crossoverPoint2 < crossoverPoint1) {
                l = crossoverPoint1;
                crossoverPoint1 = crossoverPoint2;
                crossoverPoint2 = l;
            }            

            for (int i = crossoverPoint1; i < crossoverPoint2; i++) {
                child[i] = dad[i]; //Teilpfada von 1. Elternteil uebernehmen
            }

            int fillPlacesCount = dad.length - (crossoverPoint2 - crossoverPoint1);

            int childPointer = crossoverPoint2;

            while (fillPlacesCount > 0) {


                if (crossoverPoint2 == dad.length) {
                    crossoverPoint2 = 0;   //Sprung zum Anfang wenn das Ende erreicht ist
                }
                if (childPointer == dad.length) {
                    childPointer = 0;   //Sprung zum Anfang wenn das Ende erreicht ist
                }

                if (getArrayposition(mum[crossoverPoint2], child) == -1) {
                    child[childPointer++] = mum[crossoverPoint2++];
                    fillPlacesCount--;
                } else {
                    crossoverPoint2++;
                }
            }

            newEntity.setPath(child);
            newOffspring[breedingCount] = newEntity;
        }

        return newOffspring;


    }

    public Entity[] ap(Entity[][] crossPairs) {

        Entity[] newOffspring = new Entity[crossPairs.length];















        return null;

    }

    public Entity[] cx(Entity[][] crossPairs) {

        Entity[] newOffspring = new Entity[crossPairs.length];


        for (int breedingCount = 0; breedingCount < crossPairs.length; breedingCount++) {


            int[] dad = crossPairs[breedingCount][0].getPath();
            int[] mum = crossPairs[breedingCount][1].getPath();
            int[] child = new int[dad.length];
            Entity newEntity = new Entity(dad.length);
            Random rand1 = new Random();
            int search = rand1.nextInt(dad.length - 1);
            int loopGuard = 0;
            boolean loop = false;



            while (dad[search] == mum[search] && !loop) {     //verhindert Problem,dass ersten beide Elemente gleich sind
                search = rand1.nextInt(dad.length - 1);
                loopGuard++;
                if (loopGuard > 2 * dad.length - 1) {  //falls Elemente gleich sind wird hier die Suche abgebrochen
                    loop = true;
                }               
            }
            if (loop) {
                newEntity.setPath(dad);
                newOffspring[breedingCount] = newEntity;
            } else {  //recombination

                boolean[] visited = new boolean[dad.length];
                Arrays.fill(visited, false);

                int run = 0;
                int temp = search;
                int first = temp;
                visited[temp] = true;
                child[temp] = dad[temp];
                temp = getArrayposition(mum[temp], dad);

                while (temp != first) {                    
                    run++;
                    visited[temp] = true;
                    child[temp] = dad[temp];
                    temp = getArrayposition(mum[temp], dad);

                }

                for (int i = 0; i < child.length; i++) {
                    if (!visited[i]) {
                        child[i] = mum[i];
                    }
                }

                newEntity.setPath(child);
                newOffspring[breedingCount] = newEntity;
            }
        }
        return newOffspring;

    }

    public int getRandomWithoutX(int x, int max) {
        boolean found = false;
        int random = 0;
        while (!found) {
            random = new Random().nextInt(max);
            if (random != x) {
                found = true;
            }
        }
        return random;
    }

    public int getArrayposition(int item, int[] array) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == item) {
                return i;
            }
        }
        return -1;
    }
}
